package com.ljc;

import com.ljc.dto.TreeNode;

/**
 * @author clj
 * @date 2022/12/5
 * @desc
 * 计算从根节点到叶子节点的，每条路径上结节点之和，是否等于给定的目标值，只要其中一个路径节点之和等于给定的目标值，则返回true，否则返回false。
 *
 * Given the root of a binary tree and an integer targetSum,
 * return true if the tree has a root-to-leaf path such that adding up all the values along the path equals targetSum.
 * A leaf is a node with no children.
 * <p>
 * Example 1:
 * Input: root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22
 * Output: true
 * Explanation: The root-to-leaf path with the target sum is shown.
 * <p>
 * Example 2:
 * Input: root = [1,2,3], targetSum = 5
 * Output: false
 * Explanation: There two root-to-leaf paths in the tree:
 * (1 --> 2): The sum is 3.
 * (1 --> 3): The sum is 4.
 * There is no root-to-leaf path with sum = 5.
 * <p>
 * Example 3:
 * Input: root = [], targetSum = 0
 * Output: false
 * Explanation: Since the tree is empty, there are no root-to-leaf paths.
 */
public class E112PathSum {
    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);

        int sum = 5;

//        System.out.println(hasPathSum(root, sum));
//
//        System.out.println("------------------------");

        System.out.println(hasPathSum1(root, sum));
    }

    /**
     * 方法一：从根节点开始，每当遇到一个节点的时候，从目标值里扣除节点值，一直到叶子节点判断目标值是不是被扣完。
     */
    public static boolean hasPathSum(TreeNode root, int sum) {
        if (root == null) {
            return false;
        }
        if (root.left == null && root.right == null) {
            return sum - root.val == 0;
        }

        return hasPathSum(root.left, sum - root.val) || hasPathSum(root.right, sum - root.val);
    }

    /**
     * 方法二：声明一个变量记录已经经过的节点的值之和，每经过一个节点就加上这个节点的值，在叶子节点判断变量值是否为目标值。
     */
    public static boolean hasPathSum1(TreeNode root, int sum) {
        return helper1(root, 0, sum);
    }

    public static boolean helper1(TreeNode root, int cur, int sum) {
        if (root == null) {
            return false;
        }
        cur = cur + root.val;
//        System.out.println(root);
        if (root.left == null && root.right == null) {
//            System.out.println("if cur : " + cur);
            return cur == sum;
        } else {
//            System.out.println("else cur : " + cur);
            return helper1(root.left, cur, sum) || helper1(root.right, cur, sum);
        }
    }


}
